オブジェクトを内包する配列の検索は Array, Object, Map のどれが一番速いのか
どういうこと?
{id: number, ...}[] みたいな配列から特定の id を持つ要素を取得したい
配列も大きいし取得対象も沢山ある場合にも、あまり遅くならない方法がいい
TL;DR
Map 使うのがオススメ
件数が増えてもそんなに遅くならない
取得件数が少ないなら Array でいい
件数増えたらヤバい
あらすじ
Prisma で集計のために groupBy を使っているが、集計に使わないカラムを select 出来なくて困っている
クエリを手書きできないこともないが、将来メンテするのがダルくなりそうなので別クエリで必要なカラムを取得して JS 側で結合する事にした
結合するには {id: number, ...}[] のような配列に対して配列内にあるオブジェクトの id で検索する必要がある
どうしよう…
今回の対戦者たち
Array
前準備無し
Array.prototype.find((haystack) => haystack.id === needle) で取得
Map
new Map(haystack.map((m) => m.id), m) で生成
Map.prototype.get(needle) で取得
Object
Object.fromEntries(haystack.map((h) => [h.id, h])) で生成
object[String(needle)] で取得
前評判
Array
遅そう
Map
速そう
だけど Object の方が速そう
Object
最強
ベンチマーク
事前に探索対象の配列と探索対象の id 一覧を生成する
探索対象のオブジェクトは {id: number, text: string, created: Date, sort: number} の配列
id と sort は必須、text と created はおまけでつけた(要らんと思う)
探索対象は乱数で生成、重複あり
code:benchmark.js
console.time('setup')
const haystack = Array(100000).fill().map( (_, i) => ({ id: i + 1, text: 'hoge', created: new Date(), sort: Math.random() })).sort((a, b) => a.sort - b.sort)
const needles = Array(5000).fill().map(() => Math.floor(Math.random() * haystack.length + 1))
console.timeEnd('setup')
console.log('haystack:', haystack.length, '', 'needles:', needles.length)
// ------------------------------------------------------
console.time('find')
needles.map((needle) => haystack.find((h) => h.id === needle))
console.timeEnd('find')
// ------------------------------------------------------
console.time('map')
const haystackMap = new Map(haystack.map((h) => h.id, h)) console.timeLog('map', 'insert')
needles.map((needle) => haystackMap.get(needle))
console.timeEnd('map')
// ------------------------------------------------------
console.time('object')
const haystackObject = Object.fromEntries(haystack.map((h) => h.id, h)) console.timeLog('object', 'insert')
console.timeEnd('object')
結果
100件から10件取得
code:100-10
setup: 0.509ms
haystack: 100 needles: 10
find: 0.101ms
map: 0.145ms insert
map: 0.24ms
object: 0.148ms insert
object: 0.328ms
Array が普通に速い
というか他が前準備に時間かかりすぎていて、取得は速いが結果として赤字になっている
100件から100件取得
code:100-100
setup: 0.582ms
haystack: 100 needles: 100
find: 0.29ms
map: 0.168ms insert
map: 0.426ms
object: 0.108ms insert
object: 0.579ms
Array が遅くなってきた
取得の回数が増えると遅さが目立つ
いうても Map と Object もまあ遅い
10000件から100件取得
code:10000-100
setup: 65.357ms
haystack: 10000 needles: 100
find: 25.744ms
map: 13.09ms insert
map: 13.266ms
object: 9.437ms insert
object: 14.962ms
セットアップが遅い!
Array と Map/Object が逆転
10000件から1000件取得
code:10000-1000
setup: 38.99ms
haystack: 10000 needles: 1000
find: 98.254ms
map: 3.789ms insert
map: 4.202ms
object: 4.276ms insert
object: 5.112ms
Array が遅い
Map と Object はとにかく挿入に時間がかかる
100000件から10000件取得
code:100000-10000
setup: 197.609ms
haystack: 100000 needles: 10000
find: 12.400s
map: 52.5ms insert
map: 56.267ms
object: 131.412ms insert
object: 144.694ms
Array が使い物にならなくなった
Object の挿入が Map の挿入の2倍近くかかるようになった
1000000件から100件取得
code:1000000-100
setup: 2.720s
haystack: 1000000 needles: 100
find: 5.310s
map: 692.382ms insert
map: 693.008ms
object: 3.580s insert
object: 3.582s
Array が10000件取得よりも速くなった
Object の挿入が死ぬほど遅い
考察
Array は速くない
ただし探索大業が配列なら挿入の手間がかからないので件数が少ないなら最速
Map はバランスが良い
Object より挿入が速いが、Object より取得は遅い
Object は取得なら最強
ただしとにかく挿入が遅い、件数が増えるととくに酷い
まとめ
最初に書いた
今回は Map でいきます